package hard.寻找两个正序数组的中位数;

/**
 * 寻找两个正序数组的中位数
 *
 * @author CodeX
 * @since 2020-10-09 15:09:02
 */
public class FindMedianSortedArrays {
    /**
     * 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
     * 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
     * <p>
     * 示例 1：
     * 输入：nums1 = [1,3], nums2 = [2]
     * 输出：2.00000
     * 解释：合并数组 = [1,2,3] ，中位数 2
     * </p>
     * <p>
     * 示例 2：
     * 输入：nums1 = [1,2], nums2 = [3,4]
     * 输出：2.50000
     * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
     * </p>
     * <p>
     * 示例 3：
     * 输入：nums1 = [0,0], nums2 = [0,0]
     * 输出：0.00000
     * </p>
     * <p>
     * 示例 4：
     * 输入：nums1 = [], nums2 = [1]
     * 输出：1.00000
     * </p>
     * <p>
     * 示例 5：
     * 输入：nums1 = [2], nums2 = []
     * 输出：2.00000
     * </p>
     * <p>
     * 提示：
     * <p>
     * nums1.length == m
     * </p>
     * <p>
     * nums2.length == n
     * </p>
     * <p>
     * 0 <= m <= 1000
     * </p>
     * <p>
     * 0 <= n <= 1000
     * </p>
     * <p>
     * 1 <= m + n <= 2000
     * </p>
     * <p>
     * -106 <= nums1[i], nums2[i] <= 106
     * </p>
     * <p>
     * 数组 二分查找 分治算法
     * </p>
     */
    public static double findMedianSortedArrays(int[] m, int[] n) {
        int totalLength = m.length + n.length;
        int mid = totalLength / 2;
        if (totalLength % 2 == 1) {
            double medium = getKthElement(m, n, mid + 1);
            return medium;
        }

        double medium = (getKthElement(m, n, mid) + getKthElement(m, n, mid + 1)) / 2.0;
        return medium;
    }

    public static int getKthElement(int[] nums1, int[] nums2, int k) {
        int length1 = nums1.length, length2 = nums2.length, index1 = 0, index2 = 0;
        while (true) {
            if (index1 == length1) {
                return nums2[index2 + k - 1];
            }

            if (index2 == length2) {
                return nums1[index1 + k - 1];
            }

            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }

            int newIndex1 = Math.min(k / 2 + index1, length1) - 1;
            int newIndex2 = Math.min(k / 2 + index2, length2) - 1;
            int n1 = nums1[newIndex1];
            int n2 = nums2[newIndex2];

            if (n1 > n2) {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            } else {
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            }

//            k -= k / 2;

        }
    }
}
